package com.fjh.algorithm.页面置换算法;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @Author FJH
 * @Date 2021/6/3 9:51
 * @Desc 页面置换算法-LRU(Least Recently Used)
 */
public class LRUCache {

    /**
     * 执行用时： 24 ms , 在所有 Java 提交中击败了 23.70% 的用户
     * 内存消耗： 46.9 MB , 在所有 Java 提交中击败了 12.35% 的用户
     */

    private int cap;
    private Map<Integer, Integer> map = new LinkedHashMap<>();  // 保持插入顺序

    public LRUCache(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        if (map.keySet().contains(key)){
            int value = map.get(key);
            map.remove(key);
            // 保证每次查询后，都在末尾
            map.put(key, value);
            return value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.keySet().contains(key)) {
            map.remove(key);
        } else if (map.size() == cap) {
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            iterator.next();
            iterator.remove();
        }
        map.put(key, value);
    }

}
